A Ternary Content Addressable Memory (“TCAM”) is a type of computer memory used in certain high speed searching applications, such as routing information through a network. It is designed such that it receives a data word and searches its entire memory to see if that data word is stored anywhere in it. If the data word is found, the TCAM returns a list of one or more storage addresses where the word was found. The data word may consist of 1's 0's, and X's (“don't care” bits). For example, a TCAM might have a stored word of “10XX0” which will match any of the four search words “10000”, “10010”, “10100”, or “10110”.
TCAMs are often used in network routers, where each address has two parts: the network address, which can vary in size depending on the subnet configuration, and the host address, which occupies the remaining bits. Each subnet has a network mask that specifies which bits of the address are the network address and which bits are the host address. Routing is done by consulting a routing table maintained by the router which contains each known destination network address, the associated network mask, and the information needed to route packets to that destination. Using a TCAM for the routing table makes the lookup process very efficient. The addresses are stored using “don't care” for the host part of the address, so looking up the destination address in the TCAM immediately retrieves the correct routing entry.
TCAMs have been widely used in routers, switches, and network security appliances of high speed networks to implement packet classification rules, e.g., access control list (“ACL”) call rules. They may be used for various applications, including packet filtering, forwarding, traffic load balancing and shaping. However, a main challenge in developing these applications using TCAM is the time complexity in TCAM updates, and consistency of rule matching during the rule updates. This is because the ternary entries (each storing an ACL rule) are arranged in priority order, and adding a new ACL rule may require many TCAM entry updates, if it is to be inserted in between two existing rules in adjacent TCAM entries. For example, if a new rule is to be inserted between two existing rules, typically one of the existing rules and all rules above or below it must be shifted one space. Further, consistency of rule matching must be maintained during these updates. That is, rule matching results for packets not matching the new rule should not be altered.